package sudoku;

import java.util.*;

public class SudokuAI {
    private final boolean[][] lightGrid; // Marks cells to highlight
    private final boolean[][] sameNumGrid; // 标记与 answer 数字相同的单元格
    private int solveRow; // Row of the solved cell
    private int solveCol; // Column of the solved cell
    private int answer; // The deduced number for the solved cell
    private int[][] userGrid; // The current Sudoku grid

    public SudokuAI() {
        lightGrid = new boolean[9][9];
        sameNumGrid = new boolean[9][9];
    }

    public int solve(int[][] grid) {
        resetGrids(); // 重置 lightGrid 和 sameNumGrid
        this.userGrid = grid;
        if (solveByRowColumn()) {
            System.out.println("solveByRowColumn found answer: " + answer);
            return answer;
        }
        if (solveBySubgrid()) {
            System.out.println("solveBySubgrid found answer: " + answer);
            return answer;
        }
        if (solveByEmptyCounter()) {
            System.out.println("solveByEmptyCounter found answer: " + answer);
            return answer;
        }
        if (solveByMatrix(grid)) {
            markRow(solveRow); // 标记整行
            markColumn(solveCol); // 标记整列
            markSameNumberCells(answer); // 标记与答案数字相同的单元格
            System.out.println("solveByMatrix found answer: " + answer);
            return answer;
        }
        return 0; // 未找到答案
    }

    private boolean solveByRowColumn() {
        for (int row = 0; row < 9; row++) {
            Set<Integer> rowMissing = getMissingNumbers(getRow(row));
            for (int col = 0; col < 9; col++) {
                if (userGrid[row][col] == 0) {
                    Set<Integer> colMissing = getMissingNumbers(getColumn(col));
                    Set<Integer> intersection = new HashSet<>(rowMissing);
                    intersection.retainAll(colMissing);
                    if (intersection.size() == 1) {
                        answer = intersection.iterator().next();
                        solveRow = row;
                        solveCol = col;
                        markRow(row); // 标记整行
                        markColumn(col); // 标记整列
                        markSameNumberCells(answer); // 标记与答案数字相同的单元格
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean solveBySubgrid() {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (userGrid[row][col] == 0) {
                    int rowStart = (row / 3) * 3;
                    int colStart = (col / 3) * 3;
                    Set<Integer> subgridMissing = getMissingNumbers(getSubgrid(rowStart, colStart));
                    Set<Integer> rowMissing = getMissingNumbers(getRow(row));
                    Set<Integer> colMissing = getMissingNumbers(getColumn(col));
                    Set<Integer> intersection = new HashSet<>(subgridMissing);
                    intersection.retainAll(rowMissing);
                    intersection.retainAll(colMissing);
                    if (intersection.size() == 1) {
                        answer = intersection.iterator().next();
                        solveRow = row;
                        solveCol = col;
                        markSubgrid(rowStart, colStart); // 标记整个子宫格
                        markRow(row); // 标记整行
                        markColumn(col); // 标记整列
                        markSameNumberCells(answer); // 标记与答案数字相同的单元格
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean solveByEmptyCounter() {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (userGrid[row][col] == 0) {
                    int rowStart = (row / 3) * 3;
                    int colStart = (col / 3) * 3;
                    Set<Integer> subgridMissing = getMissingNumbers(getSubgrid(rowStart, colStart));
                    Set<Integer> rowMissing = getMissingNumbers(getRow(row));
                    Set<Integer> colMissing = getMissingNumbers(getColumn(col));
                    Set<Integer> intersection = new HashSet<>(subgridMissing);
                    intersection.retainAll(rowMissing);
                    intersection.retainAll(colMissing);

                    int[] rowArr =  mergeArrays(getRow(rowStart), getRow(rowStart+1), getRow(rowStart+2));
                    Map<Integer, Integer> rowMap = countNumbers(rowArr);

                    int[] colArr =  mergeArrays(getColumn(colStart), getColumn(colStart+1), getColumn(colStart+2));
                    Map<Integer, Integer> colMap = countNumbers(colArr);

                    int emptyRow = countEmptyRowCells(row, col);
                    int emptyCol = countEmptyColCells(row, col);

                    for (int a : intersection) {
                        boolean s = false;
                        int aRow =rowMap.getOrDefault(a, 0);
                        int aCol =colMap.getOrDefault(a, 0);

                        if ((aRow == 2) && (emptyRow==1))
                            s = true;
                        if ((aCol == 2) && (emptyCol==1))
                            s = true;
                        if ((aRow == 2) &&  (aCol == 2))
                            s = true;
//                        System.out.println(row + ", " + col + ", a:" + a + ", aRow:"+aRow+", aCol:"+aCol+ ", emptyRow:" + emptyRow+ ", emptyCol:" + emptyCol +", solve:"+ s);
                        if (s) {
                            answer = a;
                            solveRow = row;
                            solveCol = col;
                            markSubgrid(rowStart, colStart); // 标记整个子宫格
                            markRow(row); // 标记整行
                            markColumn(col); // 标记整列
                            markSameNumberCells(answer); // 标记与答案数字相同的单元格
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    public int countEmptyRowCells(int row, int col) {
        int rowStart = (row / 3) * 3; // 计算子宫格的起始行
        int colStart = (col / 3) * 3; // 计算子宫格的起始列
        int emptyCount = 0;
        for (int c = colStart; c < colStart + 3; c++) {
            if (userGrid[row][c] == 0) {
                emptyCount++;
            }
        }
        return emptyCount;
    }

    public int countEmptyColCells(int row, int col) {
        int rowStart = (row / 3) * 3; // 计算子宫格的起始行
        int colStart = (col / 3) * 3; // 计算子宫格的起始列
        int emptyCount = 0;
        for (int r = rowStart; r < rowStart + 3; r++) {
            if (userGrid[r][col] == 0) {
                emptyCount++;
            }
        }
        return emptyCount;
    }

    // 合并数组的方法
    private static int[] mergeArrays(int[]... arrays) {
        // 计算总长度
        int totalLength = 0;
        for (int[] array : arrays) {
            totalLength += array.length;
        }

        // 创建合并后的数组
        int[] mergedArray = new int[totalLength];
        int index = 0;

        // 将每个数组的元素复制到合并后的数组中
        for (int[] array : arrays) {
            for (int num : array) {
                mergedArray[index++] = num;
            }
        }
        return mergedArray;
    }

    // 统计数字出现次数的方法
    public static Map<Integer, Integer> countNumbers(int[] array) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : array) {
            // 如果数字已存在，增加计数；否则初始化为1
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        return countMap;
    }

    private Set<Integer> getMissingNumbers(int[] numbers) {
        Set<Integer> missing = new HashSet<>();
        for (int i = 1; i <= 9; i++) {
            missing.add(i);
        }
        for (int num : numbers) {
            if (num != 0) {
                missing.remove(num);
            }
        }
        return missing;
    }

    private int[] getRow(int row) {
        return userGrid[row];
    }

    private int[] getColumn(int col) {
        int[] column = new int[9];
        for (int row = 0; row < 9; row++) {
            column[row] = userGrid[row][col];
        }
        return column;
    }

    private int[] getSubgrid(int rowStart, int colStart) {
        int[] subgrid = new int[9];
        int index = 0;
        for (int row = rowStart; row < rowStart + 3; row++) {
            for (int col = colStart; col < colStart + 3; col++) {
                subgrid[index++] = userGrid[row][col];
            }
        }
        return subgrid;
    }

    public int getAnswer() {
        return answer;
    }

    public boolean[][] getSameNumGrid() {
        return sameNumGrid;
    }

    public boolean[][] getLightGrid() {
        return lightGrid;
    }

    // 标记整行
    private void markRow(int row) {
        for (int col = 0; col < 9; col++) {
            lightGrid[row][col] = true;
        }
    }

    // 标记整列
    private void markColumn(int col) {
        for (int row = 0; row < 9; row++) {
            lightGrid[row][col] = true;
        }
    }

    // 标记整个子宫格
    private void markSubgrid(int rowStart, int colStart) {
        for (int row = rowStart; row < rowStart + 3; row++) {
            for (int col = colStart; col < colStart + 3; col++) {
                lightGrid[row][col] = true;
            }
        }
    }

    // 标记与答案数字相同的单元格
    private void markSameNumberCells(int number) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (userGrid[row][col] == number) {
                    sameNumGrid[row][col] = true;
                }
                if (solveRow == row && solveCol == col) sameNumGrid[row][col] = true;
            }
        }
    }

    public void resetGrids() {
        answer = 0;
        for (int i = 0; i < 9; i++) {
            Arrays.fill(lightGrid[i], false);
            Arrays.fill(sameNumGrid[i], false);
        }
    }

    ////////////////////////////////////////////////////////////////////////////////
    /**
     * 求解数独并提供下一步操作建议
     * @param grid 9x9数独网格，0表示空格
     */
    public boolean solveByMatrix(int[][] grid) {
        // 创建可能值矩阵
        boolean[][][] possibilities = findAllPossibilities(grid);

        // 策略一：查找唯一可能值的单元格（最简单明确的策略）
        if (findSingleCandidate(possibilities)) {
            return true;
        }

        // 策略二：查找隐藏的单一候选值
        if (findHiddenSingle(grid, possibilities)) {
            return true;
        }

        // 策略三：使用指向对/三元组策略
        if (findPointingPairs(grid, possibilities)) {
            return true;
        }

        // 策略四：裸对子（Naked Pairs）
        if (findNakedPairs(grid, possibilities)) {
            return true;
        }

        // 如果以上策略都无法得出结论，找到拥有最少可能性的单元格作为建议
        findLeastPossibilitiesCell(possibilities);
        return false;
    }

    /**
     * 生成所有单元格的可能值矩阵
     */
    private boolean[][][] findAllPossibilities(int[][] grid) {
        // 创建9x9x9的矩阵，[行][列][可能的数字1-9]
        boolean[][][] possibilities = new boolean[9][9][9];

        // 初始化所有的可能性为true
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (grid[row][col] == 0) {  // 空格
                    for (int num = 0; num < 9; num++) {
                        possibilities[row][col][num] = true;
                    }
                }
            }
        }

        // 根据已有数字更新可能值
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (grid[row][col] != 0) {  // 已经有数字的格子
                    // 当前位置不需要考虑可能性
                    for (int num = 0; num < 9; num++) {
                        possibilities[row][col][num] = false;
                    }

                    // 从同行、同列和同一九宫格中删除这个数字的可能性
                    int value = grid[row][col] - 1;
                    eliminatePossibility(possibilities, grid, row, col, value);
                }
            }
        }

        return possibilities;
    }

    /**
     * 消除特定数字的可能性（行、列、宫格）
     */
    private void eliminatePossibility(boolean[][][] possibilities, int[][] grid, int row, int col, int num) {
        // 消除同行可能性
        for (int c = 0; c < 9; c++) {
            possibilities[row][c][num] = false;
        }

        // 消除同列可能性
        for (int r = 0; r < 9; r++) {
            possibilities[r][col][num] = false;
        }

        // 消除同一九宫格可能性
        int boxRow = (row / 3) * 3;
        int boxCol = (col / 3) * 3;
        for (int r = boxRow; r < boxRow + 3; r++) {
            for (int c = boxCol; c < boxCol + 3; c++) {
                possibilities[r][c][num] = false;
            }
        }
    }

    /**
     * 策略一：查找只有一个可能值的单元格
     * @return 是否找到解
     */
    private boolean findSingleCandidate(boolean[][][] possibilities) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                int possibleValue = -1;
                int count = 0;

                for (int num = 0; num < 9; num++) {
                    if (possibilities[row][col][num]) {
                        possibleValue = num;
                        count++;
                    }
                }

                if (count == 1) {
                    solveRow = row;
                    solveCol = col;
                    answer = possibleValue + 1;
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 策略二：查找隐藏的单一候选值
     * 检查某个数字在行/列/宫格中只出现在一个位置的情况
     * @return 是否找到解
     */
    private boolean findHiddenSingle(int[][] grid, boolean[][][] possibilities) {
        // 检查行中的隐藏单一候选值
        for (int row = 0; row < 9; row++) {
            for (int num = 0; num < 9; num++) {
                int count = 0;
                int lastCol = -1;

                for (int col = 0; col < 9; col++) {
                    if (grid[row][col] == 0 && possibilities[row][col][num]) {
                        count++;
                        lastCol = col;
                    }
                }

                if (count == 1) {
                    solveRow = row;
                    solveCol = lastCol;
                    answer = num + 1;
                    return true;
                }
            }
        }

        // 检查列中的隐藏单一候选值
        for (int col = 0; col < 9; col++) {
            for (int num = 0; num < 9; num++) {
                int count = 0;
                int lastRow = -1;

                for (int row = 0; row < 9; row++) {
                    if (grid[row][col] == 0 && possibilities[row][col][num]) {
                        count++;
                        lastRow = row;
                    }
                }

                if (count == 1) {
                    solveRow = lastRow;
                    solveCol = col;
                    answer = num + 1;
                    return true;
                }
            }
        }

        // 检查3x3宫格中的隐藏单一候选值
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                for (int num = 0; num < 9; num++) {
                    int count = 0;
                    int lastRow = -1;
                    int lastCol = -1;

                    for (int r = boxRow * 3; r < boxRow * 3 + 3; r++) {
                        for (int c = boxCol * 3; c < boxCol * 3 + 3; c++) {
                            if (grid[r][c] == 0 && possibilities[r][c][num]) {
                                count++;
                                lastRow = r;
                                lastCol = c;
                            }
                        }
                    }

                    if (count == 1) {
                        solveRow = lastRow;
                        solveCol = lastCol;
                        answer = num + 1;
                        return true;
                    }
                }
            }
        }

        return false;
    }

    /**
     * 策略三：查找指向对/三元组
     * 当一个数字在一个宫格内只能出现在一行或一列时，可以排除该行或列其他宫格中的该数字
     * @return 是否找到解
     */
    private boolean findPointingPairs(int[][] grid, boolean[][][] possibilities) {
        // 遍历所有3x3宫格
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                // 遍历1-9的每个数字
                for (int num = 0; num < 9; num++) {
                    // 检查这个数字是否只出现在宫格的某一行或某一列
                    boolean[] rowPresence = new boolean[3];
                    boolean[] colPresence = new boolean[3];
                    int rowCount = 0;
                    int colCount = 0;

                    for (int r = 0; r < 3; r++) {
                        for (int c = 0; c < 3; c++) {
                            int actualRow = boxRow * 3 + r;
                            int actualCol = boxCol * 3 + c;

                            if (grid[actualRow][actualCol] == 0 && possibilities[actualRow][actualCol][num]) {
                                rowPresence[r] = true;
                                colPresence[c] = true;
                            }
                        }
                    }

                    // 计算有多少行/列出现了这个数字
                    for (int i = 0; i < 3; i++) {
                        if (rowPresence[i]) rowCount++;
                        if (colPresence[i]) colCount++;
                    }

                    // 如果这个数字只出现在一行，检查这一行的其他宫格
                    if (rowCount == 1) {
                        int activeRow = -1;
                        for (int i = 0; i < 3; i++) {
                            if (rowPresence[i]) {
                                activeRow = boxRow * 3 + i;
                                break;
                            }
                        }

                        // 尝试排除该行其他宫格的可能性，并检查是否能导致唯一解
                        boolean removed = false;
                        for (int c = 0; c < 9; c++) {
                            int boxOfC = c / 3;
                            if (boxOfC != boxCol && grid[activeRow][c] == 0 && possibilities[activeRow][c][num]) {
                                // 临时复制可能性矩阵
                                boolean[][][] tempPossibilities = clonePossibilities(possibilities);
                                tempPossibilities[activeRow][c][num] = false;

                                // 查找是否导致单一候选
                                for (int checkRow = 0; checkRow < 9; checkRow++) {
                                    for (int checkCol = 0; checkCol < 9; checkCol++) {
                                        if (grid[checkRow][checkCol] == 0) {
                                            int possibleCount = 0;
                                            int lastPossible = -1;

                                            for (int n = 0; n < 9; n++) {
                                                if (tempPossibilities[checkRow][checkCol][n]) {
                                                    possibleCount++;
                                                    lastPossible = n;
                                                }
                                            }

                                            if (possibleCount == 1) {
                                                solveRow = checkRow;
                                                solveCol = checkCol;
                                                answer = lastPossible + 1;
                                                return true;
                                            }
                                        }
                                    }
                                }

                                removed = true;
                            }
                        }

                        // 如果成功排除了某些可能性，但没有找到唯一解，继续寻找
                        if (removed) {
                            continue;
                        }
                    }

                    // 如果这个数字只出现在一列，检查这一列的其他宫格
                    if (colCount == 1) {
                        int activeCol = -1;
                        for (int i = 0; i < 3; i++) {
                            if (colPresence[i]) {
                                activeCol = boxCol * 3 + i;
                                break;
                            }
                        }

                        // 尝试排除该列其他宫格的可能性，并检查是否能导致唯一解
                        boolean removed = false;
                        for (int r = 0; r < 9; r++) {
                            int boxOfR = r / 3;
                            if (boxOfR != boxRow && grid[r][activeCol] == 0 && possibilities[r][activeCol][num]) {
                                // 临时复制可能性矩阵
                                boolean[][][] tempPossibilities = clonePossibilities(possibilities);
                                tempPossibilities[r][activeCol][num] = false;

                                // 查找是否导致单一候选
                                for (int checkRow = 0; checkRow < 9; checkRow++) {
                                    for (int checkCol = 0; checkCol < 9; checkCol++) {
                                        if (grid[checkRow][checkCol] == 0) {
                                            int possibleCount = 0;
                                            int lastPossible = -1;

                                            for (int n = 0; n < 9; n++) {
                                                if (tempPossibilities[checkRow][checkCol][n]) {
                                                    possibleCount++;
                                                    lastPossible = n;
                                                }
                                            }

                                            if (possibleCount == 1) {
                                                solveRow = checkRow;
                                                solveCol = checkCol;
                                                answer = lastPossible + 1;
                                                return true;
                                            }
                                        }
                                    }
                                }

                                removed = true;
                            }
                        }

                        // 如果成功排除了某些可能性，但没有找到唯一解，继续寻找
                        if (removed) {
                            continue;
                        }
                    }
                }
            }
        }

        return false;
    }

    /**
     * 策略四：裸对子（Naked Pairs）
     * 如果一个单元（行/列/宫格）中有两个格子只能包含相同的两个数字，
     * 那么可以从该单元的其他格子中排除这两个数字
     * @return 是否找到解
     */
    private boolean findNakedPairs(int[][] grid, boolean[][][] possibilities) {
        // 检查行中的裸对子
        for (int row = 0; row < 9; row++) {
            if (checkNakedPairsInUnit(grid, possibilities, true, row)) {
                return true;
            }
        }

        // 检查列中的裸对子
        for (int col = 0; col < 9; col++) {
            if (checkNakedPairsInUnit(grid, possibilities, false, col)) {
                return true;
            }
        }

        // 检查3x3宫格中的裸对子
        for (int box = 0; box < 9; box++) {
            int boxRow = (box / 3) * 3;
            int boxCol = (box % 3) * 3;
            if (checkNakedPairsInBox(grid, possibilities, boxRow, boxCol)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 检查行或列中的裸对子
     * @param isRow true表示检查行，false表示检查列
     * @param index 行号或列号
     * @return 是否找到解
     */
    private boolean checkNakedPairsInUnit(int[][] grid, boolean[][][] possibilities, boolean isRow, int index) {
        // 存储每个格子的可能值数量和位置
        int[] counts = new int[9];
        int[][] possNums = new int[9][9];

        // 统计每个格子的可能值
        for (int i = 0; i < 9; i++) {
            int row = isRow ? index : i;
            int col = isRow ? i : index;

            if (grid[row][col] == 0) {
                int count = 0;
                for (int num = 0; num < 9; num++) {
                    if (possibilities[row][col][num]) {
                        possNums[i][count] = num;
                        count++;
                    }
                }
                counts[i] = count;
            }
        }

        // 寻找恰好有两个可能值的格子
        for (int i = 0; i < 8; i++) {
            if (counts[i] == 2) {
                for (int j = i + 1; j < 9; j++) {
                    if (counts[j] == 2 &&
                            possNums[i][0] == possNums[j][0] &&
                            possNums[i][1] == possNums[j][1]) {

                        // 找到裸对子，从其他格子中排除这两个数字
                        int num1 = possNums[i][0];
                        int num2 = possNums[i][1];

                        // 尝试排除，并检查是否导致单一候选
                        for (int k = 0; k < 9; k++) {
                            if (k != i && k != j) {
                                int row = isRow ? index : k;
                                int col = isRow ? k : index;

                                if (grid[row][col] == 0) {
                                    boolean changed = false;

                                    // 临时复制可能性矩阵
                                    boolean[][][] tempPossibilities = clonePossibilities(possibilities);

                                    if (tempPossibilities[row][col][num1]) {
                                        tempPossibilities[row][col][num1] = false;
                                        changed = true;
                                    }

                                    if (tempPossibilities[row][col][num2]) {
                                        tempPossibilities[row][col][num2] = false;
                                        changed = true;
                                    }

                                    if (changed) {
                                        // 检查是否有格子只剩一个可能值
                                        for (int checkRow = 0; checkRow < 9; checkRow++) {
                                            for (int checkCol = 0; checkCol < 9; checkCol++) {
                                                if (grid[checkRow][checkCol] == 0) {
                                                    int possibleCount = 0;
                                                    int lastPossible = -1;

                                                    for (int n = 0; n < 9; n++) {
                                                        if (tempPossibilities[checkRow][checkCol][n]) {
                                                            possibleCount++;
                                                            lastPossible = n;
                                                        }
                                                    }

                                                    if (possibleCount == 1) {
                                                        solveRow = checkRow;
                                                        solveCol = checkCol;
                                                        answer = lastPossible + 1;
                                                        return true;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        return false;
    }

    /**
     * 检查3x3宫格中的裸对子
     * @return 是否找到解
     */
    private boolean checkNakedPairsInBox(int[][] grid, boolean[][][] possibilities, int boxRow, int boxCol) {
        // 存储每个格子的可能值数量和位置
        int[] counts = new int[9];
        int[][] possNums = new int[9][9];
        int[] cellRow = new int[9];
        int[] cellCol = new int[9];

        // 统计每个格子的可能值
        int index = 0;
        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                int row = boxRow + r;
                int col = boxCol + c;

                if (grid[row][col] == 0) {
                    int count = 0;
                    for (int num = 0; num < 9; num++) {
                        if (possibilities[row][col][num]) {
                            possNums[index][count] = num;
                            count++;
                        }
                    }
                    counts[index] = count;
                    cellRow[index] = row;
                    cellCol[index] = col;
                    index++;
                }
            }
        }

        // 寻找恰好有两个可能值的格子
        for (int i = 0; i < index - 1; i++) {
            if (counts[i] == 2) {
                for (int j = i + 1; j < index; j++) {
                    if (counts[j] == 2 &&
                            possNums[i][0] == possNums[j][0] &&
                            possNums[i][1] == possNums[j][1]) {

                        // 找到裸对子，从其他格子中排除这两个数字
                        int num1 = possNums[i][0];
                        int num2 = possNums[i][1];

                        // 尝试排除，并检查是否导致单一候选
                        for (int k = 0; k < index; k++) {
                            if (k != i && k != j) {
                                int row = cellRow[k];
                                int col = cellCol[k];

                                boolean changed = false;
                                boolean[][][] tempPossibilities = clonePossibilities(possibilities);

                                if (tempPossibilities[row][col][num1]) {
                                    tempPossibilities[row][col][num1] = false;
                                    changed = true;
                                }

                                if (tempPossibilities[row][col][num2]) {
                                    tempPossibilities[row][col][num2] = false;
                                    changed = true;
                                }

                                if (changed) {
                                    // 检查是否有格子只剩一个可能值
                                    for (int checkRow = 0; checkRow < 9; checkRow++) {
                                        for (int checkCol = 0; checkCol < 9; checkCol++) {
                                            if (grid[checkRow][checkCol] == 0) {
                                                int possibleCount = 0;
                                                int lastPossible = -1;

                                                for (int n = 0; n < 9; n++) {
                                                    if (tempPossibilities[checkRow][checkCol][n]) {
                                                        possibleCount++;
                                                        lastPossible = n;
                                                    }
                                                }

                                                if (possibleCount == 1) {
                                                    solveRow = checkRow;
                                                    solveCol = checkCol;
                                                    answer = lastPossible + 1;
                                                    return true;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        return false;
    }

    /**
     * 复制可能性矩阵
     */
    private boolean[][][] clonePossibilities(boolean[][][] original) {
        boolean[][][] copy = new boolean[9][9][9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                for (int n = 0; n < 9; n++) {
                    copy[r][c][n] = original[r][c][n];
                }
            }
        }
        return copy;
    }

    /**
     * 找到拥有最少可能性的单元格
     * 作为最后的策略，返回一个合理的猜测
     */
    private void findLeastPossibilitiesCell(boolean[][][] possibilities) {
        int minPossibilities = 10;

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                int count = 0;
                int lastNum = -1;

                for (int num = 0; num < 9; num++) {
                    if (possibilities[row][col][num]) {
                        count++;
                        lastNum = num;
                    }
                }

                if (count > 0 && count < minPossibilities) {
                    minPossibilities = count;
                    solveRow = row;
                    solveCol = col;
                    answer = lastNum + 1;

                    // 如果找到只有两个可能性的单元格，可以直接返回
                    if (count == 2) {
                        return;
                    }
                }
            }
        }

        // 如果没有找到有效解，将answer设为0
        if (minPossibilities == 10) {
            answer = 0;
        }
    }

}